/*
 * @lc app=leetcode.cn id=76 lang=golang
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
func minWindow(s string, t string) string {
	smap, tmap := map[byte]int{}, map[byte]int{}
	sLen, tLen := len(s), len(t)
	for i := 0; i < tLen; i++ {
		tmap[t[i]]++
	}
	check := func() bool {
		for k, v := range tmap {
			if smap[k] < v {
				return false
			}
		}
		return true
	}

	L, R := -1, -1
	min := math.MaxInt32
	for l, r := 0, 0; r < sLen; r++ {
		if _, ok := tmap[s[r]]; ok {
			smap[s[r]]++
		}
		for check() && l <= r {
			if _, ok := tmap[s[l]]; ok {
				smap[s[l]]--
			}
			if r-l+1 < min {
				L = l
				R = l + min
			}
			l++
		}

	}

	if L == -1 {
		return ""
	}
	return s[L:R]
}

// @lc code=end

